#include<ADT.h>


template<typename Comparable>
BinarySearchTree::BinarySearchTree(const BinarySearchTree &rhs): root(nullprt){
    root = clone(rhs.root);
}
template<typename Comparable>
BinaryNode* clone(BinaryNode *t) const{
    if(t == nullptr)
        return nullptr;
    else
        return new BinaryNode(t->element, clone(t->left), clone(t->right));
}

template<typename Comparable>
bool BinarySearchTree<Comparable>::contains(const Comparable & x) const{
    return contains(x, root);
}
template<typename Comparable>
void BinarySearchTree<Comparable>::insert(const Comparable &x) {
    insert(x, root);

}
template<typename Comparable>
void BinarySearchTree<Comparable>::insert(Comparable && x) {
    insert(x, root);

}

template<typename Comparable>
void BinarySearchTree<Comparable>::remove(const Comparable &x){
    remove(x, root);
}

template<typename Comparable>
bool BinarySearchTree<Comparable>::contains(const Comparable &x, BinaryNode *t) const{
    if(t == nullptr)
        return false;
    
    if(t->element == x)
        reutn true;
    else if (t->element >x)
    {
        return contains(x, t->left);
    }
    else{
        return contains(x, t->right);
    }
    
}

template<typename Comparable>
const Comparable& BinarySearchTree<Comparable>::findMax() const{
    return ((findMax(root))->element);
}
template<typename Comparable>
const Comparable& BinarySearchTree<Comparable>::findMin() const{
    return ((findMin(root))->element);
}
template<typename Comparable>
BinaryNode* BinarySearchTree<Comparable>::findMin(BinaryNode *t) const{
    if(t == nullptr)
        return nullptr;
    while (t->left !=nullptr)
    {
        t = t->left
    }
    return t;
    
}
template<typename Comparable>
BinaryNode* BinarySearchTree<Comparable>::findMax(BinaryNode *t) const{
    if(t == nullptr)
        return nullptr;
    if(t->right == nullptr)
        return t;
    
    return findMax(t->right);
}



template<typename Comparable>
void BinarySearchTree<Comparable>::makeEmpty(){
    makeEmpty(root);
}

template<typename Comparable>
void BinarySearchTree<Comparable>::makeEmpty(BinaryNode* &t){
    if(t != nullptr){
        makeEmpty(t-left);
        makeEmpty(t->right);
        delete t;
    }
    t = nullptr;

}

template<typename Comparable>
void BinarySearchTree<Comparable>::insert(const Comparable &x, BinaryNode *root){
    if(t == nullptr)
        t = new BinaryNode(x, nullptr, nullptr);
    
    if(t->element < x)
        insert(x, t->right);
    if(t->element > x)
        insert(x, t->left);
}

template<typename Comparable>
void BinarySearchTree<Comparable>::insert(Comparable &&x, BinaryNode *root){
    if(t == nullptr)
        t = new BinaryNode(std::move(x), nullptr, nullptr);
    
    if(t->element < x)
        insert(std::move(x), t->right);
    if(t->element > x)
        insert(std::move(x), t->left);
}

template<typename Comparable>
void BinarySearchTree<Comparable>::remove(const Comparable & x ,BinaryNode * &t){
    if(t == nullptr)
        return;
    if( x < t->element)
        remove(x, t->left);
    
    else if(t->element < x)
        remove(x, t->right);
    else if( t->left != nullptr && t->right != nullptr){
        t->element = findMin(t->right)->element;
        remove(t->element, t->right);
    }
    else{
        BinaryNode * oldNode = t;
        t = (t->left != nullptr) ? t->left : t->right;
        delete oldNode;
    }
}



